

public class KMP {
    String s;
    int[] next;

    KMP(String s) {
        this.s = s;
        next = new int[s.length() + 1];
        setNext();
    }

    void setNext() {
        int i = 0, j = -1;
        next[0] = -1;
        while (i < next.length) {
            if (j == -1 || s.charAt(i) == s.charAt(j)) {
                i++;
                j++;
                if(i==s.length()) break; 
                if (s.charAt(i) != s.charAt(j)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
    }

    int search(String txt) {
        int i = 0, j = 0;
        // 省略错误检查
        while (i < txt.length() && j < s.length()) {
            if(j==-1||txt.charAt(i)==s.charAt(j)){
                i++;j++;
            }
            else{
                j=next[j];
            }
        }
        if(j==s.length()){
            return i-j;
        }

        return -1;
    }

    static int search(String txt,String pat){
        return new KMP(pat).search(txt);
    }


    public static void main(String[] args) {
        System.out.println(KMP.search("asdasdabababxabcabcas", "abababx"));
    }
}
